題幹懶人包

給一個數組，旋轉數組 K 次，K 非負數，如以下

附註：盡量想越多種解法越好，想到之後可否利用空間複雜度 O(1) 完成

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

限制式：

• 1 <= nums.length <= 2 * 104
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

解法

1. 先用 tmp 紀錄最後一段的數組切片(比方說上面那個例題，先用tmp紀錄[5, 6, 7])
2. 將nums的第k項到最後一項用0到n-k項取代([4, 5, 6, 7]被[1, 2, 3, 4]取代)
3. 最後再將tmp放回去 ([1, 2, 3]被[5, 6, 7]取代)。

缺點：

很快，但空間複雜度並非 O(1)

class Solution:
    def rotate(self, nums, k: int) -> None:
        n = len(nums)
        # k 取餘數，比方說等於n根本不用旋轉
        k %= n
        if k != 0:
            # 1
            tmp = nums[-k:]
            # 2
            nums[k:n] = nums[:n - k]
            # 3
            nums[0:k] = tmp

別人的正解

想法：

1. 首先先將整個數組翻轉一次
2. 接下來看k多少決定左邊以及右邊的分界
3. 翻轉左邊，然後翻轉右邊

1. [1,2,3,4,5,6,7] -> [7, 6, 5, 4, 3, 2, 1] 
3. [7, 6, 5, 4, 3, 2, 1] -> [5, 6, 7, 4, 3, 2, 1]
3. [5, 6, 7, 4, 3, 2, 1] -> [5, 6, 7, 1, 2, 3, 4]

所以我們該設計一個可以翻轉整個數組的函數

class Solution:
        def rotate(self, nums, k: int) -> None:
            k %= len(nums)
            
            def reverse(nums, i, j):
                while i < j:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
                    j -= 1
            
            reverse(nums, 0, len(nums)-1)
            reverse(nums, 0, k-1)
            reverse(nums, k, len(nums)-1)  

reverse 函數

可以把 i 想像成頭，j 想像成尾巴，當他們頭小於尾時倆倆交換，並各自加減一

# 比方說reverse([1, 2, 3, 4, 5, 6, 7], 0, 3)
# 第一次
[1, 2, 3, 4, 5, 6, 7] -> [4, 2, 3, 1, 5, 6, 7]
# 第二次(注意這次是2跟3交換了)
[4, 2, 3, 1, 5, 6, 7] -> [4, 3, 2, 1, 5, 6, 7]
# 準備第三次時i現在等於2，j現在等於1，因此停止

記得這裡 while 的條件最好不要設等於 (建議而已)，因為比方說今天數組的長度是奇數，那可能 i += 1、j -= 1，會遇到相同的值(i 會等於 j)，當然要看設計這個函數的需求是甚麼。

def reverse(nums, i, j):
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1